Optimization problems are considered in the framework of tropical algebra tominimize and maximize a nonlinear objective function defined on vectors over anidempotent semifield, and calculated using multiplicative conjugatetransposition. To find the minimum of the function, we first obtain a partialsolution, which explicitly represents a subset of solution vectors. Wecharacterize all solutions by a system of simultaneous equation and inequality,and show that the solution set is closed under vector addition and scalarmultiplication. A matrix sparsification technique is proposed to extend thepartial solution, and then to obtain a complete solution described as a familyof subsets. We offer a backtracking procedure that generates all members of thefamily, and derive an explicit representation for the complete solution. Asanother result, we deduce a complete solution of the maximization problem,given in a compact vector form by the use of sparsified matrices. The resultsobtained are illustrated with illuminating examples and graphicalrepresentations. We apply the results to solve real-world problems drawn fromproject (machine) scheduling, and give numerical examples.
展开▼
